
/*有一群猴子，去摘了一堆桃子

商量之后决定每天吃剩余桃子的一半

当每天大家吃完桃子之后，有个贪心的小猴都会偷偷再吃一个桃子

按照这样的方式猴子们每天都快乐的吃着桃子
直到第十天，当大家再想吃桃子时，发现只剩下一个桃子了*/

/*

    F10 = 1
    Fn = (Fn+1 + 1) * 2

    Fn = Fn-1 / 2 - 1 = (Fn-2 / 2 - 1) / 2 - 1
        = F_{n-2}/(2^2) - (1/2 + 1)
        = F_{n-3}/(2^3) - (1/(2^2) + 1/2 + 1)
        = ...
        = F_{n - (n - 1)}/(2^{n-1} - (1/2^{n-2} + ... + 1)
        = F_{1}/2^{n-1} - 2(1-1/2^{n-1}) = = (F_{1} + 2) / 2^{n-1} -  2


    F_{1} = (Fn + 2) * 2^{n-1} - 2

 */

#include <stdio.h>
#include <math.h>

int monkeyPeach_iteration() {
    int ret = 1;
    int i = 0;

    // 第9天, 第8天, ... 第1天
    for (i = 9; i > 0; i--) {
        ret = (ret + 1) * 2;
    }

    return ret;
}

// day代表第几天， 函数返回值代表第day天剩余的桃子数
// 本问题， day应该传递1
int monkeyPeach_recursive(int day) {
    if (day <= 0) {
        return 0;
    }
    int sum = 0;
    if (10 == day) { // 第10天时， 给总数加1
        sum += 1;
    } else { // 第day天的数目为第day+1天的数加1再乘以2
        sum += 2 * (monkeyPeach_recursive(day + 1) + 1);
    }

    return sum;
}

// 参数说明
// 第day天吃之前剩余remain个桃子
// F_{1} = (Fn + 2) * 2^{n-1} - 2
int monkeyPeach_formula(int day, int remain) {
    if (day <= 0) {
        return 0;
    }
    return round((remain + 2) * pow(2, day - 1) - 2);
}

int nextValue(int v) {
    // if (v & 1 == 0) { // v必定为奇数才行, 因为v+1为偶数才有可能使得(v+1)*5%4==0
    //     v++;
    // }
    while ((v + 1) * 5 % 4 != 0 || v % 5 != 0) {
        v++;
    }
    return v;
}

/*

五只猴子摘了一堆桃子，可是怎么也平分不了。
于是一致同意先去睡觉，明天再分。
夜里，一只猴子偷偷起来，先吃掉一个桃子，剩下的桃子正好平分成5份
。它蒇起自己的1份，然后再去睡觉。
过了一会，第二只猴子起来，也吃掉1个桃子，剩下的桃子也正好平分成5份。
它也藏起了自己的1份，然后再去睡觉。第三只、第四只和第五只也都依次这样做。
问最初那堆桃子至少有多少个？
 */

// 函数返回代表能否成功分, 0为成功
static int canDivide(int n, int m) {
    if (n <= 0 || m <= 0) {
        return -1;
    }

    // 不足m个或不能分m份多1个，分配失败
    if (n < m || n % m != 1) {
        return 1;
    }

    // 只有一只猴子时, 一定能分成功
    if (1 == m) {
        return 0;
    }

    int t = n - 1;

    return canDivide(t - t/m, m - 1);
}

// 分给m只猴子
int monkeyPeach2_recursive(int m) {
    int n; // 桃子数量
    for (n = 1; ; n++) {
        if (canDivide(n, m) == 0) {
            break;
        }
    }

    return n;
}

int main(int argc, char const *argv[])
{
    printf("%d\n", monkeyPeach_iteration());
    printf("%d\n", monkeyPeach_recursive(1));
    printf("%d\n", monkeyPeach_formula(10, 1));
    printf("%d\n", monkeyPeach2_recursive(5));

    // int total = 1534;
    // int i = 1;
    // for (; total >= 1; i++) {
    //     printf("%d, %d\n", i, total);
    //     total = (total / 2) - 1;
    // }

    return 0;
}
